package datastructure.graph.有向图;

import datastructure.graph.最短路径.EdgeWeightedDigraph;
import datastructure.graph.最短路径.EdgeWeightedDirectedCycle;

/**
 * @author MaoLin Wang
 * @description
 * @date 2020/8/27 5:25 下午
 */
public class TopologicalSort {
    private Iterable<Integer>order;

    public TopologicalSort(Digraph digraph) {
        DirectedCircle circle=new DirectedCircle(digraph);
        if (!circle.hasCycle()){
            DepthFirstOrder firstOrder=new DepthFirstOrder(digraph);
            order=firstOrder.reversePost();
        }
    }

    public TopologicalSort(EdgeWeightedDigraph digraph) {
        EdgeWeightedDirectedCycle circle=new EdgeWeightedDirectedCycle(digraph);
        if (!circle.hasCycle()){
            DepthFirstOrder firstOrder=new DepthFirstOrder(digraph);
            order=firstOrder.reversePost();
        }
    }

    public Iterable<Integer>order(){
        return order;
    }

    public boolean hasOrder(){
        return order!=null;
    }

    public static void main(String[] args) {
        Digraph digraph = new Digraph(13);
        digraph.addEdge(0,5);
        digraph.addEdge(0,1);
        digraph.addEdge(0,6);
        digraph.addEdge(2,0);
        digraph.addEdge(2,3);
        digraph.addEdge(3,5);
        digraph.addEdge(5,4);
        digraph.addEdge(6,4);
        digraph.addEdge(6,9);
        digraph.addEdge(7,6);
        digraph.addEdge(8,7);
        digraph.addEdge(9,10);
        digraph.addEdge(9,11);
        digraph.addEdge(9,12);
        digraph.addEdge(11,12);
        TopologicalSort sort=new TopologicalSort(digraph);
        Iterable<Integer> order = sort.order;
        System.out.println(order);
    }
}
